import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: dell
 * Date: 2023-12-19
 * Time: 19:47
 */
public class test4 {
    public static int add(int n){
        int num=n;
        int ret=0;
        for (int i=1;i<=n;i++){
            ret+=i;
        }
        return ret;
    }
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n= in.nextInt();
        int[] arr=new int[n];// n为进行几次操作
        int i=0;
        while (i<n){
            int num=in.nextInt();//连续输入两个数，中间空格
            int num1= in.nextInt();
            int sum=0;
            //求数列前num项的和
            for (int j=1;j<=num;j++) {
                //add()求第j项的值
                sum+=add(j);
            }
            //结果存入数组
            arr[i]=sum%num1;
            i++;
        }
        for (int m=0;m<n;m++){
            System.out.println(arr[m]);
        }
    }
}